package com.dataStructures.tree;

import lombok.Data;

/**
 * 二叉树
 */
public class BinaryTreeDemo {
	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		HeroNode node1 = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(2, "吴用");
		HeroNode node3 = new HeroNode(3, "卢俊义");
		HeroNode node4 = new HeroNode(4, "林冲");
		HeroNode node5 = new HeroNode(5, "关胜");

		node1.setLeft(node2);
		node1.setRight(node3);
		node3.setLeft(node5);
		node3.setRight(node4);

		tree.setRoot(node1);

		System.out.println("test pre order");
		tree.preOrder();
		System.out.println("test middle order");
		tree.infixOrder();
		System.out.println("test post order");
		tree.postOrder();
		System.out.println("前序查找");
		HeroNode node = tree.preSearch(3);
		System.out.println(node);

		System.out.println("删除前：");
		tree.preOrder();
		tree.delNode(3);
		System.out.println("删除后：");
		tree.preOrder();

	}
}

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	public void preOrder() {
		if (this.root != null) {
			this.root.preOrder();
		} else {
			System.out.println("empty");
		}
	}

	public void infixOrder() {
		if (this.root != null) {
			this.root.infixOrder();
		} else {
			System.out.println("empty");
		}
	}

	public void postOrder() {
		if (this.root != null) {
			this.root.postOrder();
		} else {
			System.out.println("empty");
		}
	}

	public HeroNode preSearch(int id) {
		if (this.root != null) {
			return this.root.preSearch(id);
		} else {
			return null;
		}
	}

	public HeroNode infixSearch(int id) {
		if (this.root != null) {
			return this.root.infixSearch(id);
		} else {
			return null;
		}
	}

	public HeroNode postSearch(int id) {
		if (this.root != null) {
			return this.root.postSearch(id);
		} else {
			return null;
		}
	}

	public boolean delNode(int id) {
		if (root != null) {
			if (root.getId() == id) {
				root = null;
				return true;
			}
			return root.delNode(id);
		} else {
			System.out.println("empty tree");
			return false;
		}
	}
}

@Data
class HeroNode {
	private int id;
	private String name;
	private HeroNode left;
	private HeroNode right;

	public HeroNode(final int id, final String name) {
		this.id = id;
		this.name = name;
	}

	public String toString() {
		final StringBuffer sb = new StringBuffer("HeroNode{");
		sb.append("id=").append(id);
		sb.append(", name='").append(name).append('\'');
		sb.append('}');
		return sb.toString();
	}

	/**
	 * 前序遍历
	 */
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}

	/**
	 * 中序遍历
	 */
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this);
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	/**
	 * 后序遍历
	 */
	public void postOrder() {
		if (this.left != null) {
			this.left.postOrder();
		}
		if (this.right != null) {
			this.right.postOrder();
		}
		System.out.println(this);
	}

	/**
	 * 前序遍历查找
	 */
	public HeroNode preSearch(int id) {
		if (this.id == id) {
			return this;
		}
		HeroNode resNode = null;
		if (this.left != null) {
			resNode = this.left.preSearch(id);
		}
		if (resNode != null) {
			return resNode;
		}
		if (this.right != null) {
			resNode = this.right.preSearch(id);
		}
		if (resNode != null) {
			return resNode;
		}
		return resNode;
	}

	/**
	 * 中序遍历查找
	 */
	public HeroNode infixSearch(int id) {
		HeroNode resNode = null;
		if (this.left != null) {
			resNode = this.left.infixSearch(id);
		}
		if (resNode != null) {
			return resNode;
		}
		if (this.id == id) {
			return this;
		}
		if (this.right != null) {
			resNode = this.right.infixSearch(id);
		}
		if (resNode != null) {
			return resNode;
		}
		return resNode;
	}

	/**
	 * 前序遍历查找
	 */
	public HeroNode postSearch(int id) {
		HeroNode resNode = null;
		if (this.left != null) {
			resNode = this.left.postSearch(id);
		}
		if (this.right != null) {
			resNode = this.right.postSearch(id);
		}
		if (resNode != null) {
			return resNode;
		}
		if (this.id == id) {
			return this;
		}
		return resNode;
	}

	/**
	 * 删除节点
	 */
	public boolean delNode(int id) {
		if (this.left != null && this.left.id == id) {
			this.left = null;
			return true;
		}
		if (this.right != null && this.right.id == id) {
			this.right = null;
			return true;
		}
		if (this.left != null) {
			boolean delFlag = this.left.delNode(id);
			if (delFlag) {
				return true;
			}
		}
		if (this.right != null) {
			boolean delFlag = this.right.delNode(id);
			if (delFlag) {
				return true;
			}
		}
		return false;
	}
}